//
// Created by song on 16-12-31.
//

#ifndef C0COMPILER_GRAPH_H
#define C0COMPILER_GRAPH_H


#include "DefUseChain.h"

class Graph {
private:
    vector<DefUseChain::Node*> &nodes;
    int nodeCount;
    int*degree; // node's id as key, node's degree as value.
    int*color;
    vector<int> removeOrderNodes;
    set<int> nodeSet;
    map<int, set<int>> edges;
    set<int> notAssignSet;
    map<DefUseChain::Node*, int> convertMap;
public:

    int k;
    Graph():
            nodes(DefUseChain::Node::list),
            degree(NULL),
            color(NULL)
    {}

    void assignRegisters(int regCount){
        init(regCount);
        set<int> nodeToRemove = nodeSet;
        color = new int[nodeCount];
        int tmpDegree[nodeCount];
        for(int node=0; node<nodeCount; node++){
            tmpDegree[node]=degree[node];
            color[node] = -1;
        }
        cout << "node remains:" << nodeToRemove.size() << endl;
        while(nodeToRemove.size()>0){
            while(findAndRemoveFirstNodeDegreeLessThanK(nodeToRemove, tmpDegree));
            findProperNodeNotAssign(nodeToRemove, tmpDegree);

        }

        cout << "node remains:" << nodeToRemove.size() << endl;
        for(int i=removeOrderNodes.size()-1; i>=0; i--){
            int node = removeOrderNodes[i];
            if(notAssignSet.count(node)>0){
                color[node] = -1;
            }else{
                color[node] = allocForNode(node);
            }
            cout << node << "   " << color[node] << endl;
        }
    }

    int getColor(DefUseChain::Node* & node){
        if(convertMap.count(node)>0){
            return color[convertMap[node]];
        }else{
            Error::nextErrorDetail << "DefUseChain::Node not found";
            Error::internal(Error::Should_Not_Happen);
        }
    }

private:

    void init(int regCount){
        k = regCount;
        removeOrderNodes.clear();
        nodeSet.clear();
        edges.clear();
        notAssignSet.clear();
        convertMap.clear();
        nodeCount = nodes.size();
        degree = new int[nodeCount];
        for(int i=0; i<nodes.size(); i++) {
            degree[i] = 0;
            nodeSet.insert(i);
            convertMap[nodes[i]] = i;
        }
        addEdges(nodes);
        if(Config::printConflictGraph){
            cout << printNet();
        }
    }


    string printNet(){
        stringstream r;
        for(int node=0; node<nodeCount; node++) {
            set<int>::const_iterator i;
            for (i = edges[node].begin(); i != edges[node].end(); i++) {
                int neighbor = (*i);
                if(node < neighbor){
                    r << node << "---" << neighbor << endl;
                }
            }
        }
        return r.str();
    }


    int allocForNode(int node){
        set<int> colorNotAllow;
        set<int>::const_iterator i;
        for(i=edges[node].begin(); i!=edges[node].end(); i++) {
            int neighbor=(*i);
            int colorNeighbor=color[neighbor];
            colorNotAllow.insert(colorNeighbor);
        }
        for(int color=0; color<k; color++){
            if(colorNotAllow.count(color)==0){
                return color;
            }
        }
        Error::nextErrorDetail << "has no color to assign";
        Error::internal(Error::Should_Not_Happen);
    }

    void addEdge(int i0, int i1){
        edges[i0].insert(i1);
        edges[i1].insert(i0);
        degree[i0]++;
        degree[i1]++;
    }

    void addEdges(vector<DefUseChain::Node*> &nodes){
        for(int i=0; i<nodes.size(); i++) {
            for(int j=i+1; j<nodes.size(); j++){
                DefUseChain::Node* n_i= nodes[i];
                DefUseChain::Node* n_j= nodes[j];
                if(n_i->conflict(n_j)){
                    addEdge(i, j);
                }
            }
        }
    }

    bool findAndRemoveFirstNodeDegreeLessThanK(set<int> & nodesToRemovedFrom, int* degree){
        int maxDegreeLessThanK=-1;
        int nodeToRemove = -1;
        bool removed=false;
        set<int>::const_iterator i;
        for(i=nodesToRemovedFrom.begin(); i!=nodesToRemovedFrom.end(); i++) {
            int node = (*i);
            int deg = degree[node];
            if (maxDegreeLessThanK < deg && deg < k) {
                maxDegreeLessThanK = deg;
                nodeToRemove = node;
                removed = true;
            }
        }
        if(removed){
            decAllNeighborsDegree(nodeToRemove, degree);
            nodesToRemovedFrom.erase(nodeToRemove);
            removeOrderNodes.push_back(nodeToRemove);
        }
        return removed;
    }

    void decAllNeighborsDegree(int node, int* degree){
        set<int>::const_iterator i;
        for(i=edges[node].begin(); i!=edges[node].end(); i++) {
            int neighbor=(*i);
            degree[neighbor]--;
        }
    }

    void findProperNodeNotAssign(set<int> & nodesToRemovedFrom, int* degree){
        bool notSet=true;
        int nodeToRm=-1;
        int minDegree= -1;
        if(nodesToRemovedFrom.size()==0){
            return;
        }
        set<int>::const_iterator i; //
        for(i=nodesToRemovedFrom.begin(); i!=nodesToRemovedFrom.end(); i++) {
            int node = (*i);
            if(notSet || degree[node]<minDegree){
                minDegree = degree[node];
                nodeToRm = node;
                notSet = false;
            }
        }
        if(notSet){
            Error::nextErrorDetail << "set is empty but it pass the check! impossible";
            Error::internal(Error::Should_Not_Happen);
        }else{
            rmNode(nodeToRm);
            nodesToRemovedFrom.erase(nodeToRm);
            notAssignSet.insert(nodeToRm);
            removeOrderNodes.push_back(nodeToRm);
        }
    }

    void rmNode(int node){
        set<int>::const_iterator i;
        for(i=edges[node].begin(); i!=edges[node].end(); i++) {
            int neighbor=(*i);
            degree[neighbor]--;
            edges[neighbor].erase(node);
        }
        edges.erase(node);
    }

};


#endif //C0COMPILER_GRAPH_H
